W8. Recurrence Relations

Author

Zakhar Podyakov

Published

October 29, 2025

1. Theory

1.1 Introduction to Sequences

A sequence is an ordered list of numbers. Formally, it’s a function that maps a subset of natural numbers (like or ) to a set of values. Each element in the sequence is called a term. We often denote a sequence by , where is the term at position .

1.1.1 Arithmetic Progression

An arithmetic progression is a sequence where the difference between consecutive terms is constant. This constant difference is called the common difference, denoted by .

  • Formula:
  • Example: The sequence is an arithmetic progression with an initial term and a common difference .
1.1.2 Geometric Progression

A geometric progression is a sequence where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio, denoted by .

  • Formula:
  • Example: The sequence is a geometric progression with an initial term and a common ratio .
1.2 Recursively Defined Sequences

A sequence is defined recursively if the definition of a term depends on previous terms. This definition requires one or more initial conditions to start the sequence.

  • Recursion or recurrence happens when the definition of a concept or process depends on a simpler version of itself.
  • Example: The Fibonacci sequence is defined recursively.
    • Recursive Definition: , , and for .
    • List of Terms:
    • Each term (after the first two) is the sum of the two preceding ones.
1.3 Series

A series is the sum of the terms of a sequence.

1.3.1 Summation (Sigma Notation)

We use sigma notation () to represent the sum of terms.

  • Notation:
    • is the index of summation.
    • is the lower limit.
    • is the upper limit.
  • Recursive Definition: and .
1.3.2 Multiplication (Pi Notation)

We use pi notation () to represent the product of terms.

  • Notation:
  • Example (Factorial): .
    • By definition, .
    • Recursive Definition: and .
1.3.3 Arithmetic Series

An arithmetic series is the sum of the terms of an arithmetic progression.

  • Formula:
1.3.4 Geometric Series

A geometric series is the sum of the terms of a geometric progression.

  • Formula: For ,
1.4 Linear Recurrence Sequences

A linear recurrence sequence is a sequence where each term is a linear combination of a fixed number of previous terms. A sequence is a linear recurrence of order if: where are fixed coefficients.

1.4.1 Solving Linear Recurrence Sequences

The goal is to find a non-recursive or closed-form formula for .

  • Algorithm for Second-Order Recurrences A second-order linear recurrence has the form .
    1. Find the Characteristic Equation: Replace with to get the characteristic equation:
    2. Find the Roots: Solve the quadratic equation for its roots, and .
    3. Determine the General Solution:
      • Case 1: Distinct Roots (): The general solution is:
      • Case 2: Repeated Roots (): The general solution is:
    4. Find the Constants: Use the initial conditions (e.g., values for and ) to create a system of two linear equations and solve for the constants and .
  • Example 1: Distinct Roots Solve with .
    1. Characteristic Equation: .
    2. Roots: , so and .
    3. General Solution: .
    4. Find Constants:
      • For : .
      • For : .
      • Solving the system gives and .
    • Final Solution: .
  • Example 2: Repeated Roots Solve with .
    1. Characteristic Equation: .
    2. Roots: , so .
    3. General Solution: .
    4. Find Constants:
      • For : .
      • For : .
    • Final Solution: .
1.4.2 The Fibonacci Sequence

The Fibonacci sequence is defined by with .

  1. Characteristic Equation: .
  2. Roots: (the golden ratio, ) and .
  3. General Solution: .
  4. Find Constants: Using and , we find and .
  5. Final Solution (Binet’s Formula):
1.5 Systems of Recurrence Sequences

Sometimes, sequences are defined in terms of each other. A system of recurrence relations can often be solved by converting it into a single higher-order recurrence relation.

  • Method:
    1. Start with a system, for example:
    2. Isolate one variable in one equation. From the first equation, .
    3. Substitute this into the other equation to eliminate that variable. To do this for , first shift the index: .
    4. Now substitute both expressions for and into the second equation:
    5. Simplify to get a single recurrence relation: .
    6. Solve this new relation using the standard algorithm. You may need to compute initial values (like ) from the original system.

2. Definitions

  • Sequence: An ordered list of elements, typically numbers, defined by a function from the natural numbers to a set of values.
  • Arithmetic Progression: A sequence where the difference between any two consecutive terms is constant.
  • Geometric Progression: A sequence where the ratio between any two consecutive terms is constant.
  • Recursion: A method of defining something (like a function or sequence) in terms of itself.
  • Series: The sum of the terms in a sequence.
  • Arithmetic Series: The sum of the terms in an arithmetic progression.
  • Geometric Series: The sum of the terms in a geometric progression.
  • Linear Recurrence Sequence: A sequence where each term is a linear combination of a fixed number of preceding terms.
  • Characteristic Equation: An algebraic equation derived from a linear recurrence relation, whose roots are used to find the closed-form solution of the sequence.

3. Formulas

  • Arithmetic Progression:
  • Geometric Progression:
  • Second-Order Recurrence General Solution (Distinct Roots ):
  • Second-Order Recurrence General Solution (Repeated Root ):

4. Practice

4.1. Solve Recurrence Sequences (Lab 7, Task 1)

Solve the following recurrence sequences.

Click to see the solution

(a) Arithmetic Sequence: This is an arithmetic sequence with first term 15 and common difference -4.

  • Answer: .

(b) Geometric Sequence: This is a geometric sequence with first term -1 and common ratio -2.

  • Answer: .

(c) Linear Homogeneous Recurrence:

  • Characteristic equation: .
  • Roots are .
  • General solution: .
  • Use initial conditions:
    • .
    • .
  • Solving gives .
  • Answer: .

(d) Linear Homogeneous Recurrence (Repeated Roots):

  • Characteristic equation: .
  • Repeated root .
  • General solution: .
  • Use initial conditions:
    • .
    • .
  • Answer: .
4.2. Rewrite and Solve Systems of Recurrence Sequences (Lab 7, Task 2)

Rewrite recursively the following systems of recurrence sequences and solve (find a general solution).

Click to see the solution

(a) First System:

  1. From the first equation, .
  2. From the second equation, .
  3. Substitute : .
  4. From the first equation shifted by one index: .
  5. Substitute the expression for : .
  6. The single recurrence is .
  7. Characteristic equation: . Roots are .
  8. General Solution: .

(b) Second System:

  1. From the first equation, .
  2. From the first equation shifted by one index: .
  3. Substitute the second original equation: .
  4. Substitute the expression for : .
  5. The single recurrence is .
  6. Characteristic equation: . Roots are .
  7. General Solution: .
4.3. Formulate a Recurrence Relation (Lab 7, Task 3)

Find the number of sequences of length over the alphabet that do not contain two consecutive zeros or two consecutive ones.

Click to see the solution
  1. Define Subproblems: Let be the total number of such sequences. Let be the number of valid sequences of length ending with 0, 1, and 2, respectively.
  2. Formulate Relationships:
    • .
    • A sequence ending in 0 cannot be preceded by a 0. So it must be preceded by a 1 or a 2. Thus, .
    • A sequence ending in 1 cannot be preceded by a 1. So it must be preceded by a 0 or a 2. Thus, .
    • A sequence ending in 2 can be preceded by anything. Thus, .
  3. Combine to a Single Recurrence:
    • .
    • .
    • Since , we have .
  4. Find Initial Conditions:
    • : “0”, “1”, “2”. Total .
    • : “01”, “02”, “10”, “12”, “20”, “21”, “22”. Total .
    • Check: . We need . Let’s define (the empty string). Then . Correct.
Answer: The recurrence relation is with initial conditions .
4.4. Formulate a Recurrence for Password Combinations (Lab 7, Task 4)

A password is a combination of any of the ten digits 0-9, the 52 letters, and the eight special characters +, -, _, &, %, *, (, ). Any letter or special character has to be followed by a digit. Determine the number of possible passwords whose length is eight.

Click to see the solution
  1. Define Subproblems: Let be the number of valid passwords of length . To find a recurrence, we consider how a valid password of length can be formed.
  2. Case Analysis:
    • Case 1: The password ends with a digit. A password of length ending with a digit can be formed by taking any valid password of length and appending one of the 10 digits. Number of ways: .
    • Case 2: The password ends with a letter or special character. This is not possible. By the rules, a letter or special character must be followed by a digit. This means the last character can never be a letter or special character.
  3. Let’s redefine: Let be the number of valid passwords of length ending in a digit. Let be the number of valid passwords of length ending in a letter/special char.
    • The total is .
    • To get a string ending in a digit, we can append a digit to any valid string of length . So .
    • To get a string ending in a letter/special char (60 options), we can append it to any valid string of length that ends in a digit. So .
  4. Combine:
    • . This is not a single recurrence yet.
    • Substitute .
    • .
  5. Initial Conditions:
    • : 10 digits + 60 letters/specials = 70.
    • : DD (1010), LD (6010). Total = 100+600=700.
    • Check: ? Let’s define (empty password). Then . Incorrect.
    • The issue is in . A digit can follow a digit or a letter/special. So . Correct. A letter can only follow a digit. . Correct. Ah, is 60, is 10. . . . .
    • The recurrence is .
  6. Calculate :
    • .
    • … This is tedious to do by hand.
Answer: The recurrence is with .
4.5. Formulate a Recurrence Relation (Lab 7, Task 5)

Formulate a recurrence relation and provide initial conditions for the number of ways to partition a segment of length into segments of length 1, 2, and 3, such that there are no three consecutive segments of length 1.

Click to see the solution
  1. Define Subproblems: Let be the total number of ways. Let’s consider the last segment added.
    • Case 1: The last segment is of length 3. The remaining segment has length . There are ways.
    • Case 2: The last segment is of length 2. The remaining segment has length . There are ways.
    • Case 3: The last segment is of length 1. The preceding segment cannot be two consecutive 1s. This is more complex.
  2. Refine Subproblems: Let be the total ways. Let be the number of ways ending with exactly one 1. Let be the number of ways ending with exactly two 1s.
    • A valid partition of length can be formed by:
      • Adding a segment of length 3 to any valid partition of length .
      • Adding a segment of length 2 to any valid partition of length .
      • Adding a segment of length 1. This can only be done if the partition of length does not end in two 1s.
  3. Alternative Approach: Let be the number of ways. Consider the last segment.
    • If it’s a 3, we have ways.
    • If it’s a 2, we have ways.
    • If it’s a 1, the previous segment could be a 2 or a 3, or a 1.
      • If the end is …2,1, we have ways.
      • If the end is …3,1, we have ways.
      • If the end is …1,1, the segment before that must be a 2 or a 3.
        • …2,1,1 gives ways.
        • …3,1,1 gives ways.
  4. Simpler Recurrence: Let be the number of valid partitions. A valid partition of length can be formed by appending:
    • a ‘3’ to a valid partition of length . (Number of ways: )
    • a ‘2’ to a valid partition of length . (Number of ways: )
    • a ‘1’ to a valid partition of length that doesn’t end in ‘11’. How to count this?
    • Let’s try a direct recurrence. A valid partition must end in 2, 3, 12, 13, 112, or 113. This is too complex.
  5. Let’s go back to the first simple idea and correct it. Let be the total ways.
    • Last piece is 2: ways.
    • Last piece is 3: ways.
    • Last piece is 1: The remaining partition of length must be valid. Total ways is . BUT we must subtract the cases where this leads to an invalid partition. The only invalid case is appending a ‘1’ to a partition of length that already ends in ‘11’. How many such partitions are there? A partition of length ending in ‘11’ must have been formed from a valid partition of length that did not end in ‘1’. The last piece before the ‘11’ must have been a ‘2’ or a ‘3’. This is the number of valid partitions of length plus the number of valid partitions of length . This is getting complicated.
  6. Let’s try again:
    • (ways ending in 2) + (ways ending in 3) + (ways ending in 1)
    • Ways ending in 1: must come from a partition of length ending in 2 or 3, or a partition of length ending in 2 or 3, followed by a 1.
    • Let’s find the first few terms:
      • a(1): “1” (1 way)
      • a(2): “2”, “11” (2 ways)
      • a(3): “3”, “12”, “21” (3 ways). Note “111” is forbidden.
      • a(4): “13”, “22”, “31”, “112”, “121”, “211” (6 ways)
      • a(5): “23”, “32”, “113”, “122”, “212”, “1121”, “1211”, “2112”, “221”, “311”, “32” (11 ways).
    • The sequence 1, 2, 3, 6, 11… requires a recurrence relation. Let be the total number of ways. We can break this into cases based on the last digit(s).
    • Let be ways not ending in 1. Then .
    • Let be ways ending in 1. Then .
    • is formed by adding 1 to a partition of not ending in ‘11’. A partition of ends in ‘11’ if it came from a partition of not ending in ‘1’, which is .
    • So, .
  7. Final Attempt:
    • : Total ways for length .
    • A valid sequence can be obtained by:
      1. Appending a ‘2’ to any valid sequence of length . (Ways: )
      2. Appending a ‘3’ to any valid sequence of length . (Ways: )
      3. Appending a ‘1’ to a valid sequence of length which does not end in ‘11’.
    • How many valid sequences of length end in ‘11’? A sequence of length ending in ‘11’ must have come from a valid sequence of length by appending ‘11’. That sequence of length must not end in ‘1’. The number of ways to form a sequence of length not ending in ‘1’ is the number of ways to form it ending in ‘2’ or ‘3’, which is .
    • This is not the intended simple path. Let’s try the most direct recurrence.
    • . This is for partitions into 1,2,3 with no restrictions.
    • With the restriction, a sequence ending in ‘111’ is forbidden.
    • . The problem is in the first term.
    • Ways to add a 1: The previous sequence of length cannot end in ‘11’.
    • Number of sequences of length that end in ‘11’: These must come from a valid sequence of length by adding ‘11’. Any valid sequence of length is fine. So there are such sequences.
    • So, number of valid ways to add a ‘1’ is .
    • This gives the recurrence: .
  8. Find Initial Conditions:
    • (“1”)
    • (“2”, “11”)
    • (“3”, “12”, “21”)
    • Check: . Correct.
Answer: The recurrence relation is with initial conditions .
4.6. Formulate a Recurrence for Bitstrings without Consecutive Ones (Lab 7, Task 6)

What is the number of bitstrings of length , consisting of zeros and ones, in which no two ones are consecutive?

Click to see the solution
  1. Define Subproblems: Let be the total number of valid bitstrings of length . To find a recurrence, we can count the strings based on their last digit.
    • Let be the number of valid bitstrings of length that end in a 0.
    • Let be the number of valid bitstrings of length that end in a 1.
  2. Formulate Relationships:
    • The total number is the sum of the two types: .
    • A valid string of length ending in 0 can be formed by appending a ‘0’ to any valid string of length . Therefore, .
    • A valid string of length ending in 1 can only be formed by appending a ‘1’ to a valid string of length that ends in a ‘0’. Therefore, .
  3. Combine to a Single Recurrence:
    • Substitute the relationships into the total sum: .
    • We know that .
    • This gives the Fibonacci recurrence relation: .
  4. Find Initial Conditions:
    • For : “0”, “1”. So .
    • For : “00”, “01”, “10”. So .
    • (Note: These are the standard Fibonacci numbers, but shifted. ).
Answer: The recurrence relation is with initial conditions .
4.7. Rewrite a System of Recurrence Relations (Lab 7, Task 7)

Rewrite the following recursive system as a single second-order recurrence for :

Click to see the solution
  1. Isolate : From the first equation, we can write .
  2. Advance the Index: Since the equations hold for any , they also hold for . The first equation becomes:
    • .
  3. Substitute to Eliminate : Use the second original equation, , to replace in the equation from step 2.
    • .
  4. Substitute to Eliminate : Now use the expression from step 1, , to replace the remaining .
    • .
  5. Simplify:
    • .
Answer: The single second-order recurrence for is .
4.8. Represent a Sum Recursively (Tutorial 7, Task 1)

Represent the sum recursively.

Click to see the solution
  1. Define the Base Case: The sum for is the starting point.
    • .
  2. Find the Recursive Step: Express the sum for in terms of the sum for .
    • .
    • The first terms are equal to .
    • .
Answer: The recursive representation is , .
4.9. Represent a Sum using a Known Function (Tutorial 7, Task 2)

Represent the sum using the function .

Click to see the solution
  1. Express as a Difference of Sums: The sum from 15 to can be found by taking the sum from 1 to and subtracting the sum of the terms we don’t want, which are the terms from 1 to 14.
  2. Write the formula:
    • .
  3. Use the function S(n):
    • The first part is the sum up to , which is .
    • The second part is the sum up to 14, which is .
Answer: The representation is .
4.10. Represent Factorial Recursively (Tutorial 7, Task 3)

Represent the factorial function recursively.

Click to see the solution
  1. Define the Base Case: The factorial for is the starting point.
    • . (Often, the base case is defined as ).
  2. Find the Recursive Step: Express the factorial of in terms of the factorial of .
    • .
    • The product of the first terms is equal to .
    • .
Answer: The recursive representation is , .
4.11. Represent a Product using Factorials (Tutorial 7, Task 4)

Represent the product using the factorial function .

Click to see the solution
  1. Express as a Quotient of Products: The product from 4000 to can be found by taking the full product from 1 to and dividing by the product of the terms we don’t want, which are the terms from 1 to 3999.
  2. Write the formula:
    • .
    • .
  3. Use the factorial function:
    • The numerator is the product up to , which is .
    • The denominator is the product up to 3999, which is .
Answer: The representation is .
4.12. Solve a Recurrence Sequence (Tutorial 7, Task 5)

Solve the recurrence sequence: , .

Click to see the solution
  1. Write the Characteristic Equation: The recurrence corresponds to the characteristic equation .
  2. Find the Root: The root is .
  3. Write the General Solution: The general solution is of the form .
  4. Use the Initial Condition to Find c: We are given .
    • .
    • This gives .
  5. Write the Final Answer: Substitute the value of c back into the general solution.
    • .
Answer: .
4.13. Solve a Recurrence Sequence (Tutorial 7, Task 6)

Solve the recurrence sequence: , .

Click to see the solution
  1. Write the Characteristic Equation: The recurrence corresponds to the characteristic equation .
  2. Find the Root: The root is .
  3. Write the General Solution: The general solution is of the form .
  4. Use the Initial Condition to Find c: We are given .
    • .
    • This gives .
  5. Write the Final Answer: Substitute the value of c back into the general solution.
    • .
Answer: .
4.14. Solve a Recurrence Sequence (Tutorial 7, Task 7)

Solve the recurrence sequence: .

Click to see the solution
  1. Write the Characteristic Equation: The recurrence corresponds to the characteristic equation .
  2. Find the Roots: The roots are and .
  3. Write the General Solution: The general solution is of the form .
  4. Use the Initial Conditions to Find Constants:
    • For : .
    • For : .
  5. Solve the System:
    • Adding the two equations: .
    • Substitute back: .
  6. Write the Final Answer:
    • .
Answer: .
4.15. Solve a Recurrence Sequence (Tutorial 7, Task 8)

Solve the recurrence sequence: .

Click to see the solution
  1. Write the Characteristic Equation: The recurrence corresponds to the characteristic equation .
  2. Find the Roots: The equation is . We have a repeated root .
  3. Write the General Solution: For a repeated root, the general solution is .
  4. Use the Initial Conditions to Find Constants:
    • For : .
    • For : .
  5. Write the Final Answer:
    • .
Answer: .
4.16. Formulate a Recurrence Relation (Tutorial 7, Task 9)

Formulate a recurrence relation and provide initial conditions for the number of binary sequences of length over the alphabet that do not contain two consecutive zeros or two consecutive ones.

Click to see the solution
  1. Define Subproblems: Let be the total number of valid sequences of length . To find a recurrence, we can count the sequences based on their last digit.
    • Let be the number of valid sequences of length that end in a 0.
    • Let be the number of valid sequences of length that end in a 1.
  2. Formulate Relationships:
    • The total number of sequences is .
    • If a sequence of length ends in a 0, the preceding character must have been a 1. This means it was formed by appending a 0 to a valid sequence of length that ended in a 1. Thus, .
    • Similarly, if a sequence of length ends in a 1, the preceding character must have been a 0. Thus, .
  3. Combine to a Single Recurrence:
    • . This is incorrect.
    • Let’s re-evaluate: A valid sequence of length ending in 0 is an extension of any valid sequence of length ending in 1. So .
    • A valid sequence of length ending in 1 is an extension of any valid sequence of length ending in 0. So .
    • The problem is that the sequences are alternating. Let’s find the first few terms manually.
      • : 0, 1 (Total )
      • : 01, 10 (Total )
      • : 010, 101 (Total )
  4. Conclusion: For any length , there are only two such sequences: one starting with 0 (e.g., 01010…) and one starting with 1 (e.g., 10101…). The recurrence relation is simply for .
Answer: The initial condition is . The recurrence relation is for all .
4.17. Rewrite a System of Recurrence Relations (Tutorial 7, Task 10)

Rewrite the following system of recurrence relations as a single second-order recurrence for :

Click to see the solution
  1. Isolate : From the first equation, we can write .
  2. Advance the Index: Since the equations hold for any , they also hold for .
    • .
  3. Substitute to Eliminate : Use the second original equation to replace .
    • .
  4. Substitute to Eliminate : Now use the expression from step 1 to replace .
    • .
  5. Simplify:
    • .
Answer: The single second-order recurrence for is .